//字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 
//
// 
//
// 示例： 
//
// 
//输入：S = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca", "defegde", "hijhklij"。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
// 
//
// 
//
// 提示： 
//
// 
// S的长度在[1, 500]之间。 
// S只包含小写字母 'a' 到 'z' 。 
// 
// Related Topics 贪心 哈希表 双指针 字符串 👍 749 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * 划分字母区间
 * @date 2022-06-20 09:56:12
 */
class P763_PartitionLabels{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P763_PartitionLabels().new Solution();
	 }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> partitionLabels(String s) {
		List<Integer> res = new ArrayList<>();
		int[] last = new int[26];
		int n = s.length();
		for (int i = 0; i < n; i++) {
			last[s.charAt(i) - 'a'] = i;//记录字母出现的最后位置
		}
		int start = 0,end = 0;
		for (int i = 0; i < n; i++) {
			end = Math.max(end,last[s.charAt(i)-'a']);//end用于存储每个字母最大的位置
			if(i == end){//i到达最大位置后，进行切分
				res.add(end - start + 1);
				start = end + 1;
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
}
